package com.kongge.algorithm.demo;

import java.util.HashMap;
import java.util.Map;

/**
 * 请实现一个函数复制一个复杂链表，在复杂链表中，每个节点除了有一个next指针指向下一个结点之外，还有一个sibling指向任意结点或者null。
 * @author gaoshiqi
 *
 */
public class CloneComplexListDemo implements IAlgorithm {

	public void execute() {
		ComplexNode<Integer> nodeA = new ComplexNode<Integer>(1);
		ComplexNode<Integer> nodeB = new ComplexNode<Integer>(2);
		ComplexNode<Integer> nodeC = new ComplexNode<Integer>(3);
		ComplexNode<Integer> nodeD = new ComplexNode<Integer>(4);
		ComplexNode<Integer> nodeE = new ComplexNode<Integer>(5);
		nodeA.next = nodeB;
		nodeB.next = nodeC;
		nodeC.next = nodeD;
		nodeD.next = nodeE;
		
		nodeA.sibling = nodeC;
		nodeB.sibling = nodeE;
		nodeD.sibling = nodeB;
		
		
		ComplexNode<Integer> copyHeadNode = cloneComplexList(nodeA);
		ComplexNode<Integer> tempNode = copyHeadNode;
		while (tempNode != null) {
			System.out.print(tempNode.value + " ");
			tempNode = tempNode.next;
		}
	}
	
	private ComplexNode<Integer> cloneComplexList(ComplexNode<Integer> headNode) {
		if (headNode == null) {
			return null;
		}
		ComplexNode<Integer> copyHeadNode = null;
		// hashmap保存了新旧结点的对应关系，使复杂度降低到O(n)
		Map<ComplexNode<Integer>, ComplexNode<Integer>> nodeMap = new HashMap<CloneComplexListDemo.ComplexNode<Integer>, CloneComplexListDemo.ComplexNode<Integer>>();
		// 第一步：依次复制node结点，并保存到hashmap中
		ComplexNode<Integer> node = headNode;
		while (node != null) {
			ComplexNode<Integer> copyNode = new ComplexNode<Integer>();
			copyNode.value = node.value;
			if (copyHeadNode == null) {
				copyHeadNode = copyNode;
			}
			nodeMap.put(node, copyNode);
			node = node.next;
			copyNode = copyHeadNode.next;
		}
		
		// 第二步：复制next 和 sibling指针
		node = headNode;
		ComplexNode<Integer> tempNode = copyHeadNode;
		while (node != null) {
			ComplexNode<Integer> nextNode = node.next;
			ComplexNode<Integer> copyNextNode = nodeMap.get(nextNode);
			tempNode.next = copyNextNode;
			
			ComplexNode<Integer> siblingNode = node.sibling;
			ComplexNode<Integer> copySiblingNode = nodeMap.get(siblingNode);
			tempNode.sibling = copySiblingNode;
			
			node = node.next;
			tempNode = tempNode.next;
		}
		
		return copyHeadNode;
	}
	
	private static class ComplexNode<T> {
		T value;
		ComplexNode<T> next; // 下一结点
		ComplexNode<T> sibling; // 兄弟结点
		
		public ComplexNode() {
		}
		
		public ComplexNode(T value) {
			this.value = value;
		}
		
		public ComplexNode(T value, ComplexNode<T> next, ComplexNode<T> sibling) {
			this.value = value;
			this.next = next;
			this.sibling = sibling;
		} 
	}

}
